Modern communications systems, particularly wireless systems and cable modem systems, are subject to intermittent, random bursts of noise and interference. When such bursts occur, errors may be introduced into packets of data transmitted over the system. These errors typically affect multiple consecutive symbols of transmitted data. One common technique to minimize the impact of burst errors on a communication channel is to interleave the sequence of data symbols to be sent before its transmission. Interleaving is the process of separating consecutive data symbols and reordering the symbols for transmission. This technique distributes the impact of burst errors across a data sequence in a data transmission allowing for more effective error correction.
A block interleaver is a simple, yet effective, type of interleaver. A block interleaver writes received data symbols in a row-wise fashion in memory and then reads the symbols in a column-wise fashion to generate the interleaved sequence of data for transmission. A conventional block interleaver 110 is shown in FIG. 1. The interleaver 110 comprises a write module 120 which receives data symbols, a memory 130, and a read module 140 which reads the symbols from memory 130 in an interleaved fashion. Memory 130 may be partitioned into one or more sections.
FIG. 2 illustrates a logical representation of a block of data stored in memory 130. Data block X is segmented into symbols X11 through XMk. A block of data can be logically described in terms of a matrix. In the present example, data block X has a width N, a depth M, and has k symbols in the last row. As is standard convention, this block of data is denoted as (N, M, k). The size of the data block X is its width multiplied by its depth (i.e., S=N×M). A block of data is considered full if its last row is full (i.e., k=N).
Memory 130 can also be logically represented as a two-dimensional matrix. The memory represented in FIG. 2 is configured for a block interleaver having a width N and a depth M. A block interleaver having this configuration is commonly referred to as an N×M block interleaver.
FIG. 2 may be used to illustrate current techniques for interleaving data in a conventional block interleaver 110. In the conventional interleaver 110, write module 120 writes data symbols from data block X into memory 130 in a row by row fashion, resulting in the creation of M rows. Row 201 represents the first N symbols received and row 203 represents the last k symbols received. The read module 140 then reads the symbols in a column by column fashion starting with the M symbols in the first column 211, then the M symbols in the second column 212, and so on until the symbols in last column 214 are read.
Note that symbol X21 stored in column 211, row 202 cannot be read by read module 140 until the entire first row 201 has already been written by write module 120. In effect, all columns except the first column 211 of the block cannot be read until all rows except the last row 203 of the block have been written.
In one conventional technique, write module 120 writes a set of data symbols to a first section 134 of memory 130. Read module 140 then completely reads the symbols from the first section 134 before the next set of symbols can be input into the first memory section 134. This technique reduces memory requirements because the system requires only enough memory to hold a single block of data at a time. However, the throughput of the interleaver is highly bursty.
In another conventional technique, write module 120 writes a set of symbols from a data block to a first section 134 of memory 130. As read module 140 reads a symbol from first section 134, write module 120 writes a symbol from the next data block to a second section 138 of memory 130. The second section of memory 130 is not occupied by the data block currently being output. By alternating reads and writes in this fashion, the interleaver ensures that the write module 120 will never overwrite data stored in memory that has not yet been read by read module 140. This technique allows data to be input and output at a constant rate. However, the memory requirements for the system are significantly increased because the device must maintain memory sufficient to hold at least two blocks of data simultaneously.
A need therefore exists for a block interleaver that can reduce memory overhead while achieving constant latency.